package com.zhangxin.designmode.oop.demo4;

/**
 * @author zhangxin
 * @date 2022/4/11
 */
public class KMP {

    public static void main(String[] args) {

        String aStr = "7stydf8yyf87rfur9ue9rf9fyay89RAGF98Aug9rr9ug8u9ug8r7GFRGJRIU09GRrug8r09";
        String bStr = "9ug8u9ug8r";
        int kmp = kmp(aStr.toCharArray(), 32, bStr.toCharArray(), 6);
        System.out.println(kmp);


        System.out.println(System.currentTimeMillis());
    }

    public static int kmp(char[] a, int m, char[] b, int n) {
        int[] next = getNexts(b, n);
        int j = 0;
        for (int i = 0; i < m; ++i) {
            while (j > 0 && a[i] != b[j]) {
                j = next[j - 1] + 1;
            }
            if (a[i] == b[j]) {
                ++j;
            }
            if (j == n) {
                return i - n + 1;
            }
        }
        return -1;
    }

    private static int[] getNexts(char[] b, int n) {
        int[] next = new int[n];
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < n; ++i) {
            while (k != -1 && b[k + 1] != b[i]) {
                k = next[k];
            }
            if (b[k + 1] == b[i]) {
                ++k;
            }
            next[i] = k;
        }
        return next;
    }
}
